Explanation of Mathematics

Prime numbers are defined as numbers whose only factors are themselves and 1. The first ten primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. It should be noted that 1 is not considered a prime number. This is perhaps because 1 is the identity number. If numbers are not prime, then they are composite, meaning they have multiple factors. When broken down completely, all their facts are prime numbers. In fact, the fundamental theorem of arithmetic states that any integer greater than one has a unique factorization of prime numbers. Prime factorization is something taught as early as the fifth grade, but the actual proof of the fundamental theorem is far beyond the pay grade of a fifth grader, and even beyond many adults.

Another important theorem regarding primes is that there are infinitely many of them. The theorem is mentioned in the history section as first appearing in Euclid's 9th installment of "Elements". The proof employs condtradiction and goes as such:

Suppose there is only a finite number of prime numbers, $p_1, p_2,...p_n.$ Then suppose that $B$ is the integer that occurs when one multiplies all of the prime numbers and adds one: \[B=p_1\cdot p_2 \cdot ... p_n +1\] $B$ was not included in the known list of finite prime numbers. However, none of the primes divide $B$ because we added 1. Therefore, the only divisors of $B$ are $B$ and 1, meaning that it is a prime, contradicting the assumption that there is a finite number of primes (Languasco & Perelli, 2003).

Primes allow for many interesting properties. One theorem regarding primes is that a positive integer $p$ is prime if and only if when $p$ divides $ab$, then either $p$ divides $a$ or $p$ divides $b$. FOr example, if $p=13, a=91$, and $b=74$ then $ab=6734$, and since this is divisible by 13, that implies that one or both of 91 or 74 must be divisible by 13 as well.

Related to Euclid's findings regarding perfect numbers, it was found that if a number of the form $2^n-1$ is prime, then $n$ is prime. Numbers of this form are called Mersenne numbers, named after Marin Mersenne, a monk who lived in Paris in the 17th century. Some examples of Mersenne primes are $3 (2^2-1), 7 (2^3-1),$ and $3 (2^5-1)$. When Mersenne numbers are also prime, it provides much information - the Mersenne number is prime, $n$ is prime, and multiplying the Mersenne prime by itself yields a perfect number. Thus, when new Mersenne primes are identified, a new perfect number is identified as well (Hoffman, 1988).

Another property of primes is that if a number doesn't have any factors between 2 and its square root, then that number is prime. This property is somewhat similar to the Sieve of Eratosthenes, an important method for finding many prime numbers. The Sieve is very useful as it allows one to determine if any number less than or equal to a number $n$ is prime or composite. However, it is limited to smaller numbers, as it involves checking all the multiples of the numbers up to $\sqrt{n} $. Too large of a number would take far too much time and computational power to employ the Sieve.

With $n=49$, the Sieve works as follows. The applet below is useful to follow along throughout the instructions.

Since 1 is not considered prime, move on to 2. 2 is the first prime. Click the checkbox next to 2 to remove all multiples of 2. Move on to the next number, 3. Since 3 did not disappear, it is known that is is not a multiple of 2, so its only divisors are itself and 1, making it the next prime. Now, click the checkbox next to 3 to remove all remaining multiples of 3.

Move on to the next prime, 5. Click the checkbox next to 5 to remove all multiples. There are few left that haven't already been eliminated. Repeat with the rest of the checkboxes.

Note that after 7, clicking the checkboxes don't make any more numbers disappear, because there are only primes remaining. Therefore, the largest number needed to test was 7, which is the square root of 49.

After completing the example, it is easy to see that using the Sieve is not realistic for a very large number, like 1,392,067. However, it is very useful for checking the smaller numbers (Wesstein, 2004).

Prime numbers are also important in the realm of modular arithmetic. While it may seem like a tangent, this discussion will be useful in understanding the application of primes in cryptography.

In modular arithmetic, two integers $a$ and $b$ are said to be congruent modulo $n$ when $a-b=nk$. Congruence is denoted by the symbol $\equiv$. For example, $ 16 \equiv 2 mod 7$ because $16-2=7 \cdot 2. 23 \equiv 2 mod 7$ because $23-2=7\cdot 3$. Another important example to note is that $14 \equiv 0 mod 7$ because $14-0 = 2*7$.

Congruence classes are also important to consider when discussing modular arithmetic, and some understanding is needed to understand the discusison of basic cryptography. Congruence classes are denoted as $[\mathbb{Z}]_n$, and read as "$Z$ modulo $n$". Congruence classes are defined as follows: Let $a$ be an integer, then the congruence class of $[a]_n$ is the set of integers $b$ where $a \equiv b$ modulo $n$. $[\mathbb{Z}]_n$ behaves very differently than the integers. There are $n-1$ congruence classes in $[\mathbb{Z}]_n : [0]_n, [1]_n, [2]_n,$ and so on until $[n-1]_n$. Since $n \equiv 0$ modulo $n$, the congruence class of $[n]_n$ is really the class $[0]_n$. For example, $[\mathbb{Z}]_4$ contains $[0]_4, [1]_4, [2]_4,$ and $[3]_4$.

Consider the example for some elements of $[2]_5$, an element of $[\mathbb{Z}]_5$:

$...-28 \equiv -23 \equiv -18 \equiv -13 \equiv -8 \equiv -3 \equiv 2 \equiv 7 \equiv 12 \equiv 17 \equiv 32 \equiv 37 \equiv 42 \equiv 47 ...$

After some consideration, it is seen that each of these numbers are congruent to 2 modulo 5. $=3 \equiv 2 mod 5$ because $2- (-3) = 5 \cdot 0, 7\equiv 2 mod 5$ because $ 7-2 = 5 \cdot 1, 32 \equiv 2 mod 5$ because $ 32-2 = 5 \cdot 6$, and so on.

Arithmetic can be done with congruence classes. They can be added, subtracted, and multiplied. Equations can be solved in $[\mathbb{Z}]_n$, such as $x^2+[1]_5=[0]_5.$ These equations can be solved by checking all the elements of $[\mathbb{Z}]_5$, like so:

$x$	$x^2+[1]_5=[0]_5$
$[0]_5$	$([0]_5) ^2 +[1]_5 = [1]_5$
$[1]_5$	$([1]_5)^2+[1]_5 = [2]_5$
$[2]_5$	$([2]_5)^2+[1]_5=[4]_5+[1]_5=[5]_5 \equiv [0]_5$
$[3]_5$	$([3]_5)^2+[1]_5 = [9]_5 +[1]_5 \equiv [0]_5$
$[4]_5$	$([4]_5)^2+[1]_5=[16]_5+[1]_5=[17]_5 \equiv [2]_5$

Thus, the solutions to the equation are $[2]_5$ and $[3]_5$ (Hungerford, 2014).

Primes have useful properties in the realm of modular arithmetic, and these properties also make them useful in cryptography. Since the only divisors of a prime $p$ are itself and 1, if $ab=0$ in $[\mathbb{Z}]_p$, then $a$ or $b$ is zero. If $p$ is not a prime, say in $[\mathbb{Z}]_6$, then $ab=0$ has infinite solutions- $a=3$ and $b=2$, $a=3$ and $b=4$, $a=4$ and $b=6$, etc. This property is utilized heavily in cryptography.